package 动态规划;

/**
 * 72. 编辑距离
 * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
 *
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 解题思路：
    1：创建一个二维数组dp:其中dp[i][j]表示将word1中的前i个字符转换为word2中的前j个字符所需要的最小操作数；
    2：初始化边界条件： 0代表空字符串
        dp[0][j] = j:将空字符串转换为word2的前j个字符需要插入 j 个字符；
        dp[i][0] = i: 将word1中的前i个字符转换为空字符串需要删除 i 个字符。
    3：状态转移： 存在当前位相等与当前位不相等的情况
        假如当前位相等word1[i-1] == word2[j-1],不需要额外操作的，所以:dp[i][j] = dp[i-1][j-1];
        假如当前位不相等word1[i-1] != word2[j-1], 则会有如下三种选择的情况（每一种都可以适用）：
            如果需要插入操作，则 dp[i][j] = dp[i][j-1] + 1;
            如果需要删除操作，则 dp[i][j] = dp[i-1][j] + 1;
            如果需要替换操作，则 dp[i][j] = dp[i-1][j-1] + 1;
        每一次在这三种情况中取最小值；
    4:结果，dp[m][n] 即为将 word1 转换为 word2 所需的最少操作次数，其中 m 和 n 分别是 word1 和 word2 的长度。
 */
public class L_72 {

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // 定义二维状态数组
        int[][] dp = new int[m+1][n+1];

        // 初始化边界条件
        // 空字符串第一列边界条件初始化
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        // 空字符串第一行边界条件初始化
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m ; i++) {
            for (int j = 1; j <= n ; j++) {
                // 当前位置字符串相等
                if (word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else { // 当前位置字符串不相等
                    // 三种情况,取最小值
                    dp[i][j] = Math.min(Math.min(dp[i][j-1] + 1,dp[i-1][j] + 1),dp[i-1][j-1] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        L_72 l_72 = new L_72();
        String word1 = "horse";
        String word2 = "ros";
        int distance = l_72.minDistance(word1, word2);
        System.out.println("编辑距离: " + distance);
    }
}
